package com.camus.algorithm.impl;

import com.camus.algorithm.SubsetAlgorithm4Int;

/**
 * 递归算法求目标和的子集
 * 
 * @author jie.deng
 *
 */
public class SubsetAlgorithmOfRecursion4IntEg implements SubsetAlgorithm4Int {

	@Override
	public int[] findSubsetOfTargetSum(int[] candidateArr, int target) {
		// 递归
		return findSubsetOfTargetSum(candidateArr, target, 0, new boolean[candidateArr.length]);
	}

	public int[] findSubsetOfTargetSum(int[] candidateArr, int target, int nextCandidateIdx, boolean[] flagArr) {
		int len = candidateArr.length;
		// 1.递归终止条件
		if (target == 0) {
			return filterSubset(candidateArr, flagArr);
		}
		if (nextCandidateIdx >= candidateArr.length) {
			return null;
		}
		// 2.当前层逻辑：可以在[nextCandidateIdx,len)中选择一个
		for (int i = nextCandidateIdx; i < len; i++) {
			flagArr[i] = true;
			// 3.递归调用下一层
			int[] arr = findSubsetOfTargetSum(candidateArr, target - candidateArr[i], i + 1, flagArr);
			// 4.回溯
			flagArr[i] = false;

			if (arr != null) {
				return arr;
			}
		}
		return null;
	}

	private int[] filterSubset(int[] candidateArr, boolean[] flagArr) {
		int len = candidateArr.length;

		int size = 0;
		for (int i = 0; i < len; i++) {
			if (flagArr[i]) {
				size++;
			}
		}

		int[] subsetArr = new int[size];
		for (int i = len - 1; i >= 0; i--) {
			if (flagArr[i]) {
				subsetArr[--size] = candidateArr[i];
			}
		}
		return subsetArr;
	}

}
